class Solution {
public:
    int trap(vector<int>& height) {
        int begin = 0, end = height.size() - 1;
        int max_left = height[begin], max_right = height[end];

        int result = 0;
        while (begin < end) {
            if (height[begin] > max_left) max_left = height[begin];
            if (height[end] > max_right) max_right = height[end];
            if (height[begin] < height[end]) {
                result += max_left - height[begin];
                begin++;
            }
            else {
                result += max_right - height[end];
                end--;
            }
        }
        return result;

    }
};
